#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7, maxn = 1e3+10;
typedef long long ll;
string in;
int k;
int f[maxn], A[maxn], d[maxn][maxn], C[maxn][maxn];
void up(int &a, int b) {a = a+b>mod? a+b-mod: a+b;}
void pre(){
    for (int i = 1; i <= 1000; ++i) {
        int t = i, cnt = 0;
        while (t!=1){
            t = __builtin_popcount(t);
            ++cnt;
        }
        f[i] = cnt;
    }

    for (int i = 0; i <= 1e3; ++i) {
        C[i][0] = 1;
    }
    for (int i = 1; i <= 1e3; ++i) {
        for (int j = 1; j <= 1e3; ++j) {
            C[i][j] =(C[i-1][j-1] + C[i-1][j])%mod;
        }
    }
}

int dp(int p, int cnt, int need, bool flg){
    if(need-cnt > p)
        return 0;
    if(p==0)
        return cnt == need;
    if(flg)
        return C[p][need-cnt];
    int x = flg?1:A[p];
    int ans = 0;
    for (int i = 0; i <= x; ++i) {
        up(ans, dp(p-1, cnt+(i==1), need, flg||i<x));
    }
    if(flg) d[p][cnt] = ans;
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    pre();
    cin >> in >> k;
    if(k==0) return cout << 1, 0;
    if(k==1) return cout << in.size()-1, 0;
    int p = 0;
    for (int i = in.size()-1; i >=0 ; --i) {
        A[++p] = in[i]-'0';
    }
    int ans = 0;
    for (int i = 1; i <= 1e3; ++i) {
        if(f[i] == k-1)
            up(ans, dp(p, 0, i, false));
    }
    cout << ans;
    return 0;
}